package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder

/*
https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html

700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:
输入：root = [4,2,7,1,3], val = 5
输出：[]
 */
class leetcode_700 {
    @Test
    fun test_1() {
        val root = TreeNode(4)
        val n2 = TreeNode(2)
        val n7 = TreeNode(7)
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        root.left = n2
        root.right = n7
        n2.left = n1
        n2.right = n3

        val actual = printLevelOrder(searchBST(root, 2))
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(arrayListOf(2), arrayListOf(1, 3))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val root = TreeNode(4)
        val n2 = TreeNode(2)
        val n7 = TreeNode(7)
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        root.left = n2
        root.right = n7
        n2.left = n1
        n2.right = n3

        val actual = printLevelOrder(searchBST(root, 5))
        val expect: ArrayList<ArrayList<Int>> = arrayListOf()
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
        // 二叉搜索树的特点：左孩子 < 节点 < 右孩子。已经决定了搜索方向，不需要考虑使用哪种遍历法，也不需要考虑回溯
        // return searchBST1(root, `val`)
        return searchBST2(root, `val`)
    }

    fun searchBST1(root: TreeNode?, `val`: Int): TreeNode? {
        // 迭代法 : 指针法

        // T - LogN
        // S - 1
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return null
        }

        // 3 确定单层递归的处理逻辑：非递归，按照大小顺序
        var p: TreeNode? = root
        while (p != null) {
            if (p.`val` == `val`) {
                return p
            } else if (`val` < p.`val`) {
                p = p.left
            } else if (`val` > p.`val`) {
                p = p.right
            }
        }
        return null
    }

    fun searchBST2(root: TreeNode?, `val`: Int): TreeNode? {
        // 递归法

        // T - LogN
        // S - 1

        // 结束条件
        if (root == null || `val` == root.`val`) {
            return root
        }

        if (`val` < root.`val`) {
            return searchBST2(root.left, `val`)
        }

        if (`val` > root.`val`) {
            return searchBST2(root.right, `val`)
        }
        return null
    }
}